Şu sorun için bir yaklaşım algoritması arıyorum: Döngülerle, ağırlıksız, doğrulanmamış bir grafiğim var ve belirli bir düğümden başlayarak en uzun yolu bulmak istiyorum. Performans üzerinde hıza değer veriyorum (bu nedenle bir O (n^5) algoritması muhtemelen bir aşırı sıkma olabilir).Verilen bir düğümden en uzun yol yaklaşımı algoritması
Bu ev ödevi değildir (yemin ederim!) Veya ilgili işler, ancak sahip olabileceğiniz herhangi bir ipucunu takdir edeceğim.
aşağıdaki sorunu için bir yaklaşım algoritması arıyorum ...
Bilim adamları yanı bunun için arıyoruz. Ayrıca P ≠ NP ise, polinom sabit faktör yaklaşımının bulunmadığı proved'a sahiptir. Ve this makalesinin özeti, sorununuz için bir yaklaşım algoritması içerdiğini iddia ediyor.
Vay, bunu bilmiyordum. Genelleşmiş problemin sabit faktör yaklaşımı algoritması olduğunu düşündüm. Problemi daha da sınırlamaktan kaçının, sabit olan en fazla sayıda komşuya sahip olmak ne demektir? – r0u1i
@ r0u1i, Bağlandığım ilk makalede Whoops, bu tür kısıtlamaların yardımcı olmadığına dair bir kanıt da içeriyor :-). –
Teşekkürler, Siz kazanın :) – r0u1i
bu google yarışma için mi? Buraya nasıl geldim, haha! – aramadia
Beni çok iyi biliyorsun :) – r0u1i