0
일부 기하학적 라우팅 알고리즘에 대해 읽었습니다. 주 알고리즘의 버전에서 경험적 방법을 사용하면 성능이 향상되지만 점근 적 최적화가 사라집니다.알고리즘에서 휴리스틱 스를 사용하면 왜 점근 적 최적 성이 제거됩니까?
왜 그런 경우입니까? 더 나은 성능보다 점근 적 최적을 선호해야합니까? 점근 적 최적 성을 선호하는 원형이 있습니까? 벤치 마크가 있습니까?
A
답변
0
휴리스틱 스가 빠르게 실행되지만 최적의 솔루션을 얻을 수없는 최적의 솔루션 찾기 알고리즘은 항상 최적의 솔루션을 제공하지만 최악의 경우 훨씬 느리게 실행될 수있는 최적화 문제에 대해 질문하는 것으로 생각합니다. 그렇다면 여기에 몇 가지 정보가 있습니다. 일반적으로 휴리스틱 알고리즘을 사용하기로 결정하는 것은 최적의 솔루션을 "실제적으로"얼마나 근사하는지에 달려 있습니다. 일반적인 솔루션 품질이 사용자에게 충분하고 특정 문제 인스턴스가 실제로 직면하게되는 문제의 범주. 관심이 있다면 NP 완전 문제에 대한 근사 알고리즘을 찾을 수 있습니다. 휴리스틱 스에서 발견 된 솔루션의 점수가 최적 솔루션 점수의 상수 승수 (1 + 엡실론) 내에있는 몇 가지 문제가 있습니다. 엡실론을 선택할 수 있습니다. 그러나 전형적으로 엡실론이 감소함에 따라 운전 시간은 증가한다.
0
내 생각에 그들은 근사 알고리즘을위한 (admissible) 휴리스틱의 사용에 대해 이야기하고 있습니다. 예를 들어, 여행 세일즈맨 문제는 NP 완전하지만, NP 완성 문제에 대해 알려진 알고리즘보다 훨씬 빠르지 만 단지 최적의 수 % 이내로 만 보장되는 heuristic approximation methods이 있습니다.
귀하의 질문에 대한 답변을 제공하기 위해 더 많은 상황을 제시해야합니다. 알고리즘을 해킹하여 알고리즘을 깨뜨릴 수있는 여러 가지 방법이 있으며 알고리즘이 손상되는 방식은 대부분 도메인 별입니다. 그래서, 어떤 알고리즘을 말하는 겁니까? – tmyklebu