Macar Algoritmasının Sıfırları Kapatma Alt Yordamı Üzerine [Pamukkale Univ Muh Bilim Derg]
Pamukkale Univ Muh Bilim Derg. 2012; 18(2): 85-94 | DOI: 10.5505/pajes.2012.30502  

Macar Algoritmasının Sıfırları Kapatma Alt Yordamı Üzerine

Murat Erşen Berberler, Onur Uğurlu, Gözde Kızılateş
Dokuz Eylül Üniversitesi, Fen Fakültesi, Bilgisayar Bilimleri Bölümü, İzmir

Macar algoritması bilgisayar bilimleri literatüründe en çok bilinen yöntemlerden birisidir. Bu yöntem ile maliyet matrisi her adımda sistematik bir şekilde yeni bir indirgenmiş matrise dönüştürülerek atama problemine çözüm getirilmektedir. Algoritmanın alt yordamında matriste sıfır içeren tüm hücreler en az sayıda çizgi ile kapatılmakta ve çizgilerin durumuna göre matris üzerinde işlem yapılmaktadır. Bu makalede literatürdeki en az sayıda çizgi ile kapatma teknikleri incelenecek ve yeni bir yöntem önerisinde bulunularak hesaplama denemelerinin sonuçları tartışılacaktır.

Anahtar Kelimeler: Macar algoritması, En büyük eşleme, Atama problemi.


On a Subroutine for Covering Zeros in Hungarian Algorithm

Murat Erşen Berberler, Onur Uğurlu, Gözde Kızılateş
Dokuz Eylül Üniversitesi, Fen Fakültesi, Bilgisayar Bilimleri Bölümü, İzmir

The Hungarian algorithm is one of the most well-known methods in computer science literature. By this method, in each step the cost matrix is systematically reduced to a new matrix in order to obtain an optimal solution for the assignment problem. The subroutine of the algorithm includes determining the minimum number of lines needed to cover all zeros in the reduced cost matrix and modifying the matrix according to the number of lines. In this paper, firstly the methods in literature including the covering all zeros with a minimum number of lines are examined, then a new method is proposed and computational experiments are discussed.

Keywords: Hungarian algorithm, Maximum matching, Assignment problem.


Murat Erşen Berberler, Onur Uğurlu, Gözde Kızılateş. On a Subroutine for Covering Zeros in Hungarian Algorithm. Pamukkale Univ Muh Bilim Derg. 2012; 18(2): 85-94

Sorumlu Yazar: Murat Erşen Berberler


ARAÇLAR
Tam Metin PDF
Yazdır
Alıntıyı İndir
RIS
EndNote
BibTex
Medlars
Procite
Reference Manager
E-Postala
Paylaş


Benzer makaleler
Google Scholar


 
Creative Commons Lisansı
Bu dergi Creative Commons Al 4.0 Uluslararası Lisansı ile lisanslanmıştır.


LookUs & Online Makale