해시가없는 경로는 어떻게 만드나요?

Question

나는지도의 최단 경로의 경로를 찾기 위해 노력하고 있어요 (무게/거리와 노드를 연결).

{"A"=>{"B"=>1, "E"=>1}, "B"=>{"A"=>1, "C"=>1, "F"=>1}, "C"=>{"B"=>1, "D"=>1, "G"=>1}, "D"=>{"C"=>1, "H"=>1}, "E"=>{"F"=>1, "A"=>1, "I"=>1}, "F"=>{"E"=>1, "G"=>1, "B"=>1, "J"=>1}, "G"=>{"F"=>1, "H"=>1, "C"=>1, "K"=>1}, "H"=>{"G"=>1, "D"=>1, "L"=>1}, "I"=>{"J"=>1, "E"=>1, "M"=>1}, "J"=>{"I"=>1, "K"=>1, "F"=>1, "N"=>1}, "K"=>{"J"=>1, "L"=>1, "G"=>1, "O"=>1}, "L"=>{"K"=>1, "H"=>1, "P"=>1}, "M"=>{"N"=>1, "I"=>1}, "N"=>{"M"=>1, "O"=>1, "J"=>1}, "O"=>{"N"=>1, "P"=>1, "K"=>1}, "P"=>{"O"=>1, "L"=>1}} 

가 지금은 횡단이 해시에서 경로를 만들고 싶어 :

의 내가 이런 해시를 가정 해 봅시다. 대상에 소스 A에서

: 예를 들어 L

출력은 다음과 같아야합니다 A -> E -> I -> J -> K -> L 또는 A -> B -> C -> D -> H -> L 중 하나를.

여기서 I 쓴 함수이다

def find_path(src, dst, init = []) 
    path = [src] 
    neighbors = self.neighbors(src) 
    puts "src: #{src}" 
    puts "dst: #{dst}" 
    # puts "node: #{node}" 
    puts "init: #{init}" 
    puts "path: #{path}" 
    puts "----\n" 

    if neighbors.include?(dst) 
    path.push(dst) 
    else 
    path.push(@nodes[src].keys.map{|k| k unless init.flatten.include? k }.reject(&:blank?).each{|key| self.find_path(key, dst, init << path) }) 
    end 
    return path 
end 

그러나,이 지문 만 : "A", [ "B", "E"]의 출력이 요구되지

, 아무도 나에게이 일을 어떻게 할 수 있는지 말해 줄 수 있니? 감사.

업데이트 :지도의 최단 경로 경로를 찾기 위해 사용되었습니다 https://gist.github.com/suryart/6439102이

Answer 1

원래 해시 :

h = {"A"=>{"B"=>1, "E"=>1}, "B"=>{"A"=>1, "C"=>1, "F"=>1}, "C"=>{"B"=>1, "D"=>1, "G"=>1}, "D"=>{"C"=>1, "H"=>1}, "E"=>{"F"=>1, "A"=>1, "I"=>1}, "F"=>{"E"=>1, "G"=>1, "B"=>1, "J"=>1}, "G"=>{"F"=>1, "H"=>1, "C"=>1, "K"=>1}, "H"=>{"G"=>1, "D"=>1, "L"=>1}, "I"=>{"J"=>1, "E"=>1, "M"=>1}, "J"=>{"I"=>1, "K"=>1, "F"=>1, "N"=>1}, "K"=>{"J"=>1, "L"=>1, "G"=>1, "O"=>1}, "L"=>{"K"=>1, "H"=>1, "P"=>1}, "M"=>{"N"=>1, "I"=>1}, "N"=>{"M"=>1, "O"=>1, "J"=>1}, "O"=>{"N"=>1, "P"=>1, "K"=>1}, "P"=>{"O"=>1, "L"=>1}} 

의 형식 때문에 원래의 해시를 변환 짜증 :

h.keys.each{|k| h[k] = h[k].keys} 
h.default = [] 

방법 여기이 질문에 달성하기 위해 노력했다에 대한 세부 사항은 다음과 같습니다 :

def find_path h, src, dst 
    paths = [[src]] 
    loop do 
    paths = paths.flat_map do |path| 
     h[path.last].map do |nekst| 
     a = [*path, nekst] 
     a.last == dst ? (return a) : a 
     end 
    end 
    end 
end 

은 그것을 시도 :

해결책이없는 경우, 다음 루프가 영원히 실행할 수 있음는

find_path(h, "A", "L") 
# => ["A", "B", "C", "D", "H", "L"] 

알 수 있습니다. 길이에 제한을 추가하여 제한하고자 할 수 있습니다.