안녕하세요. 언제나 궁금할때만 글을 쓰게 되네요.^^;
Shortest Path에 대해서 조사할일이 있어서 찾다보니까 약간 애매해서 이렇게 질문드립니다. 예전에 optimal이었다고 책에서 봤던거 같아서 optimal 증명을 찾아보니까 못찾겠네요. 그러면서 드는 생각이 optimal 증명이 없는거 아닐까? 그냥 아직까지 구한 알고리즘중에서는 optimal인거 아닐까? 라는 생각도 드네요. 그러면서도 compare based sorting의 optimal 증명과 비슷하게 하면 될거 같기도 하고 해서 햇갈립니다.
고수님들의 도움 부탁드립니다. (_ _)
compare based sorting 의 optimal 증명이라면 시간 면에서 optimal 한지를 물어보시는 거겠죠? ^^; 최단거리 문제의 시간에 관한 lower bound 가 딱히 있다는 말은 저도 못 들어 봤네요. ㅎㅎ 그리고 현실적으로는 A* 등의 알고리즘이 (구현에 따라) 더 나은 성능을 내고요...
아랫분이 더 자세한 답변해 주실듯? ㅋㅋ
@,.@
안녕하세요. 언제나 궁금할때만 글을 쓰게 되네요.^^;
Shortest Path에 대해서 조사할일이 있어서 찾다보니까 약간 애매해서 이렇게 질문드립니다. 예전에 optimal이었다고 책에서 봤던거 같아서 optimal 증명을 찾아보니까 못찾겠네요. 그러면서 드는 생각이 optimal 증명이 없는거 아닐까? 그냥 아직까지 구한 알고리즘중에서는 optimal인거 아닐까? 라는 생각도 드네요. 그러면서도 compare based sorting의 optimal 증명과 비슷하게 하면 될거 같기도 하고 해서 햇갈립니다.
고수님들의 도움 부탁드립니다. (_ _)
14년 전