埃德蒙茲PHP中的最大匹配算法

我在互聯網上搜索了所有嘗試在PHP中查找示例代碼，但我無法這樣做。我想要做的是將課程與課程中有一組與其兼容的房間的課程相匹配。埃德蒙茲PHP中的最大匹配算法

示例：課程A可以在房間X，Y和Z，課程B房間P和Q中教授。

每個課程可以匹配到給定時間段中的一個房間。我必須創建一個函數來接受這兩組房間和課程並輸出最大匹配。任何人都可以提供PHP的源代碼，可以讓我開始？我從來沒有建立過匹配算法，也不知道從哪裏開始。

來源

2012-03-09 user1258469

你如何存儲/檢索你的數據（課程，房間）？還是你已經到了那個地步了？ – 2012-03-09 04:17:52

僞代碼在維基百科http://en.wikipedia.org/wiki/Edmonds's_matching_algorithm，你可以從那裏開始？ – 2012-03-09 04:18:04

你正在描述的設置是一個**雙向圖**，並且有一些算法可以在二分圖中找到比Edmonds的算法快得多的最大匹配。你幾乎可以肯定會找到並實現其中一種算法。 – templatetypedef 2012-03-09 04:51:07

你可以嘗試Igor Naverniouk的library代碼爲Bipartite Matching。它是用C++編寫的，但可以輕鬆將其轉換爲PHP。

來源

2012-03-09 07:18:22

非常感謝你對我來說這絕對是一個正確的方向。但是我仍然不確定輸入矩陣的格式。進一步閱讀後，我發現PHP使用矩陣作爲二維數組。爲了使這個代碼正常工作，輸入必須是一個m×n的矩陣，如果匹配的話，它的值爲1，沒有匹配的時候的值爲0。我是否應該有一個矩陣，使得$ matrix ['course_name'] ['room_name'] = 1表示匹配，0表示不匹配，還是我必須爲每個課程名稱和房間名稱分配一個唯一編號，並將它們用作數組的索引？ – user1258469 2012-03-09 15:14:13

我認爲你應該爲每個課程和房間（從1到n）分配唯一的編號（從1到m的增量）。當然，可以修改代碼來使用名稱作爲索引，但我認爲這會有點慢。 – 2012-03-10 05:27:40

非常感謝您的幫助。你的回答非常有幫助。 – user1258469 2012-03-10 18:34:52

埃德蒙茲PHP中的最大匹配算法

回答

相關問題