我在尋找以下問題的正確的關鍵字/命名，因爲我無法找到谷歌什麼這個話題：圖搜索與邊緣類型約束
我有一個圖，其中每個邊緣和每個節點被分配給某個班級/顏色或任何你稱之爲的東西。現在我想要在開始和目標節點之間找到路徑，對路徑有一些限制。例如，我希望路徑上的「藍色」節點儘可能少，或者最少。 2個「紅色」邊緣，或者這些東西的組合。當然，也存在通常的邊緣成本，除了固定路徑約束之外，還必須將其最小化。
這種問題是如何調用的，或者我需要搜索什麼？
問候 馬克
我不認爲這樣的一個普遍問題的名稱存在。不過，我敢肯定，你可以重新模型的圖形，並通過一個簡單的Dijkstra搜索解決這個問題：
試圖避免某些（類型）的頂點：假設你有一個頂點即是避免，並有k個鄰居。將其替換爲K_k（即具有k個頂點的團），並將每個鄰居連接到k個新頂點中的一個。然後將所有派系邊的重量設置得很大。現在，在經過最初的頂點的每個路徑必須經過集團和「支付費用」，也就是說，它會是可以避免的，如果可能的話
試圖避免某些邊緣：只需相應地提高自己的優勢重量
然後，運行一個簡單的Dijkstra搜索。如果您有多個類，是要避免的，你甚至可以設置權重來確定，以避免他們每個人的優先級..
希望幫助， 盧卡斯
感謝您的想法。我也有類似的想法，但是簡單地提高邊權重並不能涵蓋所有的約束變體。假設我們想訪問一個邊緣最多3次。那麼任何包含3或更少的路徑都是完美無缺的，因此在這裏提高權重可能會導致不同（更差）的路徑選擇。一種方法是在約束不再滿足時動態地改變權重，但我不確定它是否總是產生最佳路徑。 – Jgdo
噢，現在你甚至有「相同邊緣的x倍」-constraints？您在原始文章中沒有提及這些。 恐怕你必須在任何人都能夠幫助你的情況下完全明確你的問題。 –
抱歉，我以爲我確實在這裏做過：「例如，我希望路徑上的」藍色「節點儘可能少，或者最多2個」紅色「邊緣或這些組合。」 – Jgdo