擊敗貪婪算法

對於課堂，我們有一個網格和我們需要檢測並前往的網格上的一串正方形。我們從（0,0）開始。我們每次掃描網格的微小區域（出於與我們的數據結構有關的原因，這是強制性的），以及當我們檢測到需要移動的正方形，然後我們移動時。網格上有32個位置，但我們只需要移動其中的16個位置，並且儘可能快（我們正在與其他人競爭）。擊敗貪婪算法

迪傑斯特拉的算法會找到從我們當前位置到下一個位置的最短路徑。然而，這是次優的，因爲我們的下一個位置可能離那之後的位置非常遠。如果我們能夠以某種方式計算我們掃描的位置密度，然後選擇去一個非常密集的地方並在該地區內的所有位置行駛，那將會更加有益。

是否有最適合這種情況的算法？我知道貪婪的啓發式不是最優的。 A *和Dijkstra是我們最初想到的，但我們希望有一個完全不同的解決方案。

不幸的是，這是在彙編中完成的。

來源

2010-10-28 Sam

對於Dijkstra方法爲什麼不是最優的，您是否有確切的反例？我似乎無法找到任何東西。 – IVlad 2010-10-28 21:34:32

您需要去哪些地方連接到對方？從一個位置到另一個位置的距離是否等於歐幾里德距離sqrt（dx^2 + dy^2）？或者是否有指定位置之間的道路（邊緣）和距離（重量）？ – LarsH 2010-10-28 21:45:35

裝配？可憐的你。 :( – st0le 2010-10-29 06:01:25

找到密集的點（例如，您必須訪問的位置）稱爲cluster analysis。查看幾類算法的鏈接。

彙編語言是一個非常痛苦的實驗高級算法的方法。你的教授是個虐待狂嗎？

來源

2010-10-28 21:42:16 LarsH

擊敗貪婪算法

回答

相關問題