The Crossing

An analysis of uninformed search algorithms depth first, bredth first, and uniform-cost.

The raw code for this Jupyter notebook is by default hidden for easier reading. The main focus of this particular page of the notebook is on the graphs and their interpretation. To toggle on/off the raw code, click below:

In [1]:
from IPython.paths import get_ipython_dir
from IPython.core.display import HTML  
import os  

HTML(''' 
<center><h3>
<a href="javascript:code_toggle()">Talk is cheap, show me the code.</a>
</center></h3>
<script>
    var code_show=true; //true -> hide code at first

    function code_toggle() {
        $('div.prompt').hide(); // always hide prompt

        if (code_show){
            $('div.input').hide();
        } else {
            $('div.input').show();
        }
        code_show = !code_show
    }
    $( document ).ready(code_toggle);
</script>
''')
Out[1]:

Talk is cheap, show me the code.

In [2]:
# Setup notebook theme
from jupyterthemes import get_themes
from jupyterthemes.stylefx import set_nb_theme
set_nb_theme(get_themes()[1])
Out[2]:

The Problem


Four people want to get to the other side of a river by crossing a very narrow tunnel that a maximum of two people may cross at a time. It is nighttime, so someone must carry the single flashlight during each crossing. One of them takes 1 minute to cross the tunnel, another takes 2 minutes, another takes 5 minutes, and the last takes 10 minutes to cross. Then, we name them persons 1, 2, 5, and 10, respectively. If two people cross the tunnel together, they must walk at the pace of the slower one. So, if persons 5 and 10 cross together, they take 10 minutes to get to the other side. (If person 5 crosses by himself, it takes 5 minutes.) How long does it take all four people to get to the other side? Of course, it depends on how they do it. From the initial state (1, 2, 5, and 10 on the same side with the flashlight) there are ten possible crossing actions: 1 crosses alone, 2 crosses alone, 5 crosses alone, 10 crosses alone, 1 and 2 cross, 1 and 5 cross, 1 and 10 cross, 2 and 5 cross, 2 and 10 cross, or 5 and 10 cross. (If two people cross, it doesn't matter which one holds the flashlight.)

Here is an example solution:

1 and 10 go across 10 minutes
1 goes back with light 1 minute
1 and 5 go across 5 minutes
1 goes back with light 1 minute
1 and 2 go across 2 minutes
Total 19 minutes

Optimal Solutions


At first look the example solution above may appear to be optimal but it is not. A good question is whether any of the uninformed search algorithms can find a better solution. Running the algorithms on the same group of people in the order depth-first, breadth-first, then unifrom produces the following output.

In [3]:
from search import dfs, bfs, uniform

algorithms = [dfs, bfs, uniform]
people = [1, 2, 5, 10]

# Run each algorithm
for algorithm in algorithms:
    print(algorithm(people))
24
17
17

From this output it looks like both breadth first search and uniform-cost search have found a better solution. Depth first search has found a much worse solution than the obvious, and while it is certainetly not optimal its advantage will be shown later. Are both of the algorithms that found this solution truely optimal though? Here are the results after adding one person to the group creating of persons 1, 2, 5, 10 and 1.

In [4]:
people = [1, 2, 5, 10, 1]

print("Breadth first: ", bfs(people))
print("Uniform cost:  ", uniform(people))
Breadth first:  26
Uniform cost:   17

Clearly breadth first is not always optimal, in fact it is only optimal under certain conditions. Under the condition that the path cost is a nondecreasing function of the depth of the node breadth-first search is optimal, a common case of this is when all actions have the same cost. Alternatively uniform cost search is optimal as long as it tests for goal state at expansion, not generation, time.

Execution Time


Each algorithm has different properties for execution time until a solution is found. This can be a major factor when selecting which algorithm to use.

Breadth-first search runs nicely until a group size of five people, then it sharply spikes on a group of six. After six people it runs too slow to be of any real use.

In [5]:
# Set up for graphing
import timeit
from random import seed, randint

seed(42)

# Get breadth-first search times
bfs_data = []
for i in range(6):
    temp_list = []
    for j in range(i):
            temp_list.append(randint(1, 100))
    bfs_data.append(temp_list)

bfs_times = []
for group in bfs_data:
    start_time = timeit.default_timer()
    bfs(group)
    bfs_times.append(timeit.default_timer() - start_time)
In [6]:
# Graph
import plotly.plotly as py
import plotly.graph_objs as go

# Create traces
trace0 = go.Scatter(
    x = [1, 2, 3, 4, 5, 6],
    y = bfs_times,
    mode = 'lines+markers',
    name = 'Breadth-First',
    hoverinfo='name',
    line=dict(
        shape='spline'
    )
)

data = [trace0]

# Plot
data0 = [trace0]
layout = dict(
    xaxis=dict(
        title='People in Group'
    ),
    yaxis=dict(
        title='Time',
    ),
    legend=dict(
        y=0.5,
        traceorder='reversed',
        font=dict(
            size=16
        )
    )
)
fig0 = dict(data=data0, layout=layout)
py.iplot(fig0, filename='breadth-first')
Out[6]:

Depth-first search on the other hand increases much more steadily in execution time for group size. While it can not find an optimal solution except by accident it can find a solution for a group size of about 60 in the same time it take breadth-first to find a solution for 6.

In [7]:
# Set up for graphing
seed(42)

# Get breadth-first search times
dfs_data = []
for i in range(60):
    temp_list = []
    for j in range(i):
            temp_list.append(randint(1, 100))
    dfs_data.append(temp_list)

dfs_times = []
for group in dfs_data:
    start_time = timeit.default_timer()
    dfs(group)
    dfs_times.append(timeit.default_timer() - start_time)
In [8]:
# Graph
# Create traces
trace1 = go.Scatter(
    x = list(range(60)),
    y = dfs_times,
    mode = 'lines+markers',
    name = 'Depth-First',
    hoverinfo='name',
    line=dict(
        shape='spline'
    )
)

data1 = [trace1]

# Plot
data = [trace1]
layout = dict(
    xaxis=dict(
        title='People in Group'
    ),
    yaxis=dict(
        title='Time',
    ),
    legend=dict(
        y=0.5,
        traceorder='reversed',
        font=dict(
            size=16
        )
    )
)
fig1 = dict(data=data1, layout=layout)
py.iplot(fig1, filename='depth-first')
Out[8]:

Uniform cost search runs only slightly slower than breadth-first search maxing out at a group size of five.

In [9]:
# Set up for graphing
seed(42)

# Get breadth-first search times
uniform_data = []
for i in range(6):
    temp_list = []
    for j in range(i):
            temp_list.append(randint(1, 100))
    uniform_data.append(temp_list)

uniform_times = []
for group in uniform_data:
    start_time = timeit.default_timer()
    uniform(group)
    uniform_times.append(timeit.default_timer() - start_time)
In [10]:
# Graph
# Create traces
trace2 = go.Scatter(
    x = list(range(6)),
    y = uniform_times,
    mode = 'lines+markers',
    name = 'Uniform-Cost',
    hoverinfo='name',
    line=dict(
        shape='spline'
    )
)

data2 = [trace2]

# Plot
data = [trace2]
layout = dict(
    xaxis=dict(
        title='People in Group'
    ),
    yaxis=dict(
        title='Time',
    ),
    legend=dict(
        y=0.5,
        traceorder='reversed',
        font=dict(
            size=16
        )
    )
)
fig2 = dict(data=data2, layout=layout)
py.iplot(fig2, filename='uniform-cost')
Out[10]:

Side by side comparison


It is obvious from the side-by-side comparison that depth-first search is many times faster than the others.

In [11]:
data = [trace0, trace1, trace2]
layout = dict(
        xaxis=dict(
        title='People in Group'
    ),
    yaxis=dict(
        title='Time',
    ),
    legend=dict(
        y=0.5,
        traceorder='reversed',
        font=dict(
            size=16
        )
    )
)
fig3 = dict(data=data, layout=layout)
py.iplot(fig3, filename='uninformed-search-comparison')
Out[11]: