程序代写代做代考 algorithm python Informed Search¶

Informed Search¶
Implementation of the basic informed search algorithms using NetworkXlibrary
In [1]:
# Install NetworkX, Matplotlib, Pandas, Numpy using pip package in the current Jupyter kernel
import sys
!{sys.executable} -m pip install networkx
!{sys.executable} -m pip install matplotlib
!{sys.executable} -m pip install pandas
!{sys.executable} -m pip install numpy

Requirement already satisfied: networkx in c:\users\brix\anaconda3\lib\site-packages (2.3)
Requirement already satisfied: decorator>=4.3.0 in c:\users\brix\anaconda3\lib\site-packages (from networkx) (4.4.0)
Requirement already satisfied: matplotlib in c:\users\brix\anaconda3\lib\site-packages (3.1.0)
Requirement already satisfied: cycler>=0.10 in c:\users\brix\anaconda3\lib\site-packages (from matplotlib) (0.10.0)
Requirement already satisfied: kiwisolver>=1.0.1 in c:\users\brix\anaconda3\lib\site-packages (from matplotlib) (1.1.0)
Requirement already satisfied: pyparsing!=2.0.4,!=2.1.2,!=2.1.6,>=2.0.1 in c:\users\brix\anaconda3\lib\site-packages (from matplotlib) (2.4.0)
Requirement already satisfied: python-dateutil>=2.1 in c:\users\brix\anaconda3\lib\site-packages (from matplotlib) (2.8.0)
Requirement already satisfied: numpy>=1.11 in c:\users\brix\anaconda3\lib\site-packages (from matplotlib) (1.16.4)
Requirement already satisfied: six in c:\users\brix\anaconda3\lib\site-packages (from cycler>=0.10->matplotlib) (1.12.0)
Requirement already satisfied: setuptools in c:\users\brix\anaconda3\lib\site-packages (from kiwisolver>=1.0.1->matplotlib) (41.0.1)
Requirement already satisfied: pandas in c:\users\brix\anaconda3\lib\site-packages (0.24.2)
Requirement already satisfied: pytz>=2011k in c:\users\brix\anaconda3\lib\site-packages (from pandas) (2019.1)
Requirement already satisfied: python-dateutil>=2.5.0 in c:\users\brix\anaconda3\lib\site-packages (from pandas) (2.8.0)
Requirement already satisfied: numpy>=1.12.0 in c:\users\brix\anaconda3\lib\site-packages (from pandas) (1.16.4)
Requirement already satisfied: six>=1.5 in c:\users\brix\anaconda3\lib\site-packages (from python-dateutil>=2.5.0->pandas) (1.12.0)
Requirement already satisfied: numpy in c:\users\brix\anaconda3\lib\site-packages (1.16.4)

Using our algorithm¶

Travelling in Romania¶
Import the adjacency matrix from CSV file. Includes the distances between the cities directly connected in the map.
In [1]:
import pandas as pd
import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
%matplotlib inline
import warnings
warnings.filterwarnings(“ignore”, category=UserWarning)

dfRomania = pd.read_csv(‘romania.csv’)

Change NA to 0, needed for NetworkX graph.
In [2]:
dfRomania.fillna(0, inplace=True)
dfRomania.set_index(‘city’, inplace = True)

Convert Pandas DataFrame to NetworkX Graph
In [3]:
romaniaMap = nx.from_pandas_adjacency(dfRomania, nx.Graph)

Display the roadmap
In [4]:
layout=nx.spring_layout(romaniaMap)
nx.draw_networkx(romaniaMap, layout, with_labels=True)

Heuristic function¶
Specific for our problem. Straight line distance from the actual city to Bucharest.
In [5]:
def evalHeuristic(graph, node):
dfDist = pd.read_csv(‘romaniaDist.csv’)
dfDist.set_index(‘city’, inplace=True)
return dfDist.at[node,’dist’]

A* Search¶
In [6]:
def fringeAddNode(fringeTemp, nodeName, heuristic):

# Create a tuple (node name, heuristic value) and add it to the fringe
node = (nodeName, heuristic)
fringeTemp.append(node)

return fringeTemp

def fringeExtractBest(fringeTemp):

# Order the fringe by decreasing heustic value (tup[1])
# Why Here?
fringe = fringeTemp.sort(key = lambda tup: tup[1], reverse = True)

# For debugging
print(‘Ordered Fringe:’, fringeTemp)

# Extract the node with best heuristic value (on list tail)
bestNode = fringeTemp.pop()
nodeName = bestNode[0]
nodeCost = bestNode[1]

# Return the updated fringe, the extracted node name
return fringeTemp, nodeName, nodeCost

def aStar(graph, startNode, endNode, maxSteps):
# Initialisation
# Use visited flag on each node to find if we should consider it for fringe expansion
fringe = []
currentNode = None
step = 0
costSoFar = 0

# Update navigation startup values, including heuristic value
for node in graph.nodes:
graph.nodes[node][‘parent’] = False
graph.nodes[node][‘visited’] = False
# Give a value to the heuristic of each node
graph.nodes[node][‘heuristic’] = evalHeuristic(graph, node)
# Set the cost so far of the node
graph.nodes[node][‘costSoFar’] = 0

# Setup starting point, root of the tree
fringe = fringeAddNode(fringe, startNode, graph.nodes[startNode][‘heuristic’] )
graph.nodes[startNode][‘parent’] = None

# Execute until there are nodes to be visited
while fringe:
# For debugging
#print(‘Fringe:’, fringe)

# Extract the node with the best heuristic value
# from the fringe and visit the node
fringe, currentNode, currentCost = fringeExtractBest(fringe)
print(currentNode, “->”)

# Update step count
step += 1

# Check goal
if not(currentNode == endNode):
# Check condition
if step <= maxSteps: # Update the visited flag if needed if(not graph.nodes[currentNode]['visited']): graph.nodes[currentNode]['visited'] = True # Add to fringe neighbouring nodes, if not visited for neighbour in graph.adj[currentNode]: if not graph.nodes[neighbour]['visited']: costSoFar = graph.nodes[currentNode]['costSoFar'] # Previous steps cost #print(currentNode, " cost", costSoFar) cost = graph[currentNode][neighbour]['weight'] # This step cost #print(neighbour, "to reach cost",cost) graph.nodes[neighbour]['costSoFar'] = costSoFar + cost # g(n) = previous node cost + this step strategyValue = graph.nodes[neighbour]['costSoFar'] + graph.nodes[neighbour]['heuristic'] # f(n) = g(n) + h(n) #print('heuristic',graph.nodes[neighbour]['heuristic']) #print(currentNode, neighbour, strategyValue) fringe = fringeAddNode(fringe, neighbour, strategyValue) graph.nodes[neighbour]['parent'] = currentNode else: print(" Execution ended without reaching the goal") break else: print(currentNode, " *GOAL* - Number of steps:", step, 'cost:', currentCost ) break print("- End") Visit Romania using A*¶ From Arad to Bucharest In [7]: romaniaMap['Arad']['Sibiu']['weight'] Out[7]: 140.0 In [8]: aStar(romaniaMap, 'Arad', 'Bucharest', 100) Ordered Fringe: [('Arad', 366)] Arad ->
Ordered Fringe: [(‘Zerind’, 449.0), (‘Timisoara’, 447.0), (‘Sibiu’, 393.0)]
Sibiu ->
Ordered Fringe: [(‘Oradea’, 671.0), (‘Zerind’, 449.0), (‘Timisoara’, 447.0), (‘Fagaras’, 417.0), (‘Rimnicu’, 413.0)]
Rimnicu ->
Ordered Fringe: [(‘Oradea’, 671.0), (‘Craiova’, 526.0), (‘Zerind’, 449.0), (‘Timisoara’, 447.0), (‘Fagaras’, 417.0), (‘Pitesti’, 415.0)]
Pitesti ->
Ordered Fringe: [(‘Oradea’, 671.0), (‘Craiova’, 615.0), (‘Craiova’, 526.0), (‘Zerind’, 449.0), (‘Timisoara’, 447.0), (‘Bucharest’, 418.0), (‘Fagaras’, 417.0)]
Fagaras ->
Ordered Fringe: [(‘Oradea’, 671.0), (‘Craiova’, 615.0), (‘Craiova’, 526.0), (‘Bucharest’, 450.0), (‘Zerind’, 449.0), (‘Timisoara’, 447.0), (‘Bucharest’, 418.0)]
Bucharest ->
Bucharest *GOAL* – Number of steps: 6 cost: 418.0
– End

要求:
At the last step of A* algortihm, it is difficult to understand which is the path that led to the solution. (as you can see Bucharest is present into the fringe with multiple values)
Please modify the A* algorithm to show the final path to the solution.
In [ ]:

In [ ]: