project2/p2q3-alt.rb
def plan_tour(adj_matrix, node_value, node_time, origin, dest, time_limit)
  # number of nodes in the graph
  n = adj_matrix.size
  result = nil

  # reset the destination node value to 0
  node_value[dest] = 0

  # impute node_time into adj_matrix
  adjust_matrix(adj_matrix, node_time, origin, dest)

  # run dijkstra's from Q2 to obtain shortest distances to all nodes from the
  # destination
  dest_dist = find_way_all(adj_matrix, dest)

  # visiting all nodes, consider all neighbours, pick the best (largest value)
  # node that's possible. impossible nodes are ones that are either already on
  # the traversed path, or ones that are definitely out-of-range from dest.
  #
  # nodes are definitely out-of-range if the accumulated travel time so far,
  # plus edge travel time to the node, exceeds the time limit.
  stack = [[0, origin, 0, [origin]]]

  while !stack.empty?
    value, node, acc_cost, node_path = stack.pop

    if node == dest
      result = node_path
      break
    end

    node_path_hash = Hash[node_path.map { |x| [x, nil] }]

    neighbours = []
    # examine all neighbours, collect those that are feasible
    line = adj_matrix[node]
    for d in 0...n
      if !line[d].nil?
        # only visit neighbours that are not already on this path
        if !node_path_hash.has_key?(d)
          # only visit neighbours that are not out-of-range
          if acc_cost + line[d] + dest_dist[d] <= time_limit
            # this neighbour is feasible!

            # consider the neighbour's neighbours' max value
            line2 = adj_matrix[d]
            max2 = 0.0
            sum2 = 0.0
            for d2 in 0...n
              if d != d2
                if !line2[d2].nil?
                  if !node_path_hash.has_key?(d2)
                    if acc_cost + line[d] + line2[d2] + dest_dist[d2] <= time_limit
                      m = (node_value[d] + node_value[d2]) / (line[d] + line2[d2])
                      if m > max2
                        max2 = m
                      end
                    end
                  end
                end
              end
            end

            neighbours << [max2 + node_value[d] / line[d], d, acc_cost + line[d], node_path.clone.push(d)]
          end
        end
      end
    end

    # sort by value asc, add to back of stack
    neighbours = neighbours.sort_by { |neighbour| neighbour[0] }
    stack.concat(neighbours)
  end

  return result
end
# a more interesting implementation
#
# - node touring times are imputed into edge travel times
# - dijkstra from dest to find shortest feasible path from all nodes
# - considering the max value/time heuristic when selecting which neighbour
#   to visit next, by examining the neighbour's neighbours
a more interesting implementation
node touring times are imputed into edge travel times
dijkstra from dest to find shortest feasible path from all nodes
considering the max value/time heuristic when selecting which neighbour
to visit next, by examining the neighbour's neighbours
a more interesting implementation node touring times are imputed into edge travel times dijkstra from dest to find shortest feasible path from all nodes considering the max value / time heuristic when selecting which neighbour to visit next by examining the neighbour ' s neighbours
def plan_tour(adj_matrix, node_value, node_time, origin, dest, time_limit)
  n = adj_matrix.size
  result = nil
  node_value[dest] = 0
  adjust_matrix(adj_matrix, node_time, origin, dest)
  dest_dist = find_way_all(adj_matrix, dest)
   nodes are definitely out-of-range if the accumulated travel time so far,
   plus edge travel time to the node, exceeds the time limit.
  stack = [[0, origin, 0, [origin]]]
  while !stack.empty?
    value, node, acc_cost, node_path = stack.pop
    if node == dest
      result = node_path
      break
    end
    node_path_hash = Hash[node_path.map { |x| [x, nil] }]
    neighbours = []
     examine all neighbours, collect those that are feasible
    line = adj_matrix[node]
    for d in 0...n
      if !line[d].nil?
         only visit neighbours that are not already on this path
        if !node_path_hash.has_key?(d)
           only visit neighbours that are not out-of-range
          if acc_cost + line[d] + dest_dist[d] <= time_limit
             this neighbour is feasible!
             consider the neighbour's neighbours' max value
            line2 = adj_matrix[d]
            max2 = 0.0
            sum2 = 0.0
            for d2 in 0...n
              if d != d2
                if !line2[d2].nil?
                  if !node_path_hash.has_key?(d2)
                    if acc_cost + line[d] + line2[d2] + dest_dist[d2] <= time_limit
                      m = (node_value[d] + node_value[d2]) / (line[d] + line2[d2])
                      if m > max2
                        max2 = m
                      end
                    end
                  end
                end
              end
            end
            neighbours << [max2 + node_value[d] / line[d], d, acc_cost + line[d], node_path.clone.push(d)]
          end
        end
      end
    end
     sort by value asc, add to back of stack
    neighbours = neighbours.sort_by { |neighbour| neighbour[0] }
    stack.concat(neighbours)
  end
  return result
end
def plan_tour ( adj_matrix , node_value , node_time , origin , dest , time_limit ) n = adj_matrix . size result = nil node_value [ dest ] = 0 adjust_matrix ( adj_matrix , node_time , origin , dest ) dest_dist = find_way_all ( adj_matrix , dest ) stack = [ [ 0 , origin , 0 , [ origin ] ] ] while ! stack . empty? value , node , acc_cost , node_path = stack . pop if node == dest result = node_path break end node_path_hash = Hash [ node_path . map { | x | [ x , nil ] } ] neighbours = [ ] line = adj_matrix [ node ] for d in 0 ... n if ! line [ d ] . nil? if ! node_path_hash . has_key? ( d ) if acc_cost + line [ d ] + dest_dist [ d ] <= time_limit line2 = adj_matrix [ d ] max2 = 0.0 sum2 = 0.0 for d2 in 0 ... n if d != d2 if ! line2 [ d2 ] . nil? if ! node_path_hash . has_key? ( d2 ) if acc_cost + line [ d ] + line2 [ d2 ] + dest_dist [ d2 ] <= time_limit m = ( node_value [ d ] + node_value [ d2 ] ) / ( line [ d ] + line2 [ d2 ] ) if m > max2 max2 = m end end end end end end neighbours << [ max2 + node_value [ d ] / line [ d ] , d , acc_cost + line [ d ] , node_path . clone . push ( d ) ] end end end end neighbours = neighbours . sort_by { | neighbour | neighbour [ 0 ] } stack . concat ( neighbours ) end return result end
a more interesting implementation
 node touring times are imputed into edge travel times
 dijkstra from dest to find shortest feasible path from all nodes
 considering the max value/time heuristic when selecting which neighbour
to visit next, by examining the neighbour's neighbours
a more interesting implementation node touring times are imputed into edge travel times dijkstra from dest to find shortest feasible path from all nodes considering the max value / time heuristic when selecting which neighbour to visit next by examining the neighbour ' s neighbours
# number of nodes in the graph # reset the destination node value to 0 # impute node_time into adj_matrix # run dijkstra's from Q2 to obtain shortest distances to all nodes from the # destination # visiting all nodes, consider all neighbours, pick the best (largest value) # node that's possible. impossible nodes are ones that are either already on # the traversed path, or ones that are definitely out-of-range from dest. # # nodes are definitely out-of-range if the accumulated travel time so far, # plus edge travel time to the node, exceeds the time limit. # examine all neighbours, collect those that are feasible # only visit neighbours that are not already on this path # only visit neighbours that are not out-of-range # this neighbour is feasible! # consider the neighbour's neighbours' max value # sort by value asc, add to back of stack
adj_matrix
node_value
node_time
origin
dest
time_limit