Article #217
Subject: Counting Backtracking Searches in Network Graphs
Author: Andrew W. Harrell
Posted: 11/8/2013 01:36:51 PM

When I was given the problem of improving the NATO European wargaming
mathematics around 1982 by Col. Marshall in the OSD(office of Secretary of
Defense) it took several years to solve it. At that time all the war games
used by the US Army Deputy Chief of Staff for Operations (an office named
Norman Schwartkopf) were linear push and pull weapon scores models. These
models did not portray accurately the unit-movement maneuver type war fare
based on battle position unit movements planned by the SACEUR Gen. Haig. I
was unable to solve this problem while in Washington. But, when I returned to
the Corps of Engineers Geotechnical Laboratory at Vicksburg I found what I
needed. We had at that time the best mobility information on digital maps and
some West Point Turbo Pascal programs to draw vehicle traverses and computes
speeds across the map [see my operations research papers and talks in the Who
we are section of this website]. This combined with a $50 version Turbo
Prolog enabled me overlay movement networks on the maps and solve
the "obstacle effectiveness" problem which quantified the importance of
engineer units to the European Scenario.

Somewhat later I sent in a mathematical paper on the details of how to
computer the number of paths through these networks. It was never published.

But, most of it is in the references mentioned above. But, a good way to
simplify the calculations of the number of these paths has to my knowledge
not been discovered yet.



I am still working on this problem and would appreciate anyone else's ideas
about how to do it.



Here is some text from a talk I gave about it last year at the Am. Math.
Society Convention in San Diego:



----------------------------------------

The well-known Ford-Fulkerson algorithm and most of the approaches to solving
the network maximal flow and minimal-cost problems use a labeling procedure.
In this paper an alternative approach is examined which makes use of the full
ordered list of flow paths without cycles. The list is generated by a Prolog-
based depth-first search with backtracking of the type described by Winston
[5].



------------------------------------



Rationale for using a Backtracking search



Digital map network mobility routing problems are best solved by a multiple
start point, multiple end point, path searching, goal seeking, backtracking
algorithm

The algorithm extends partial paths by sorting non-cyclic routes at each new
search stage.

It solves both the max-flow and minimal cost throughput problem.

The networks allow bidirectional edges.

Unit/ task resource scheduling problems can be solved by adding work time to
network nodes

The method differs from other depth-first search procedures in that it saves
information about partial solution paths. This allows a better evaluation of
the effect of a competitive military war gaming situation were it is
possible to remove edges of the network from the solution





--------------------------------------





References



1] Harrell,A.W., “ A Logic Programming Approach to Network Flow
Algorithms”, Transactions on the Eight Army Conference on Applied
Mathematics , ARO Report 91-1, pp 577-609. also the above report is available
in downloadable pdf form at
http://www.yhwhschofchrist.org/5073/NetCombLogic1.pdf

2] Harrell,A.W., “ The Concept of Individual Vehicular and Unit Mobility and
its Effect on wargaming”, Proceedings 27th Army Operations Research
Symposium, Vol. II,pp.3-993 to 3-1006,1988.

3] Harrell,A.W., “ The Concept of Individual Vehicular and Unit Mobility and
its Effect on wargaming”, Proceedings 56th Military Operation Research
Symposium, 1989.

4] Harrell, A.W., “Evaluating the Effect of Off-Rod Obstacles on Unit
Movement”, Technical Report GL -89-4, U.S. Army Engineering Research and Dev.
Lab, Vicksburg, MS, 1989

5] Winston, Patrick Henry, Artificial Intelligence 2nd ed., Addison Wesley,
Reading, MA, 1984.

6] Ford, L.R. and Fulkerson, D.R., Flows in Networks, Princeton University
Press, Princeton, NJ., 1962



--------------------------------------------------

Call a node a critical backtracking node if it has more than one edge
proceeding from it and more than one edge entering it.

Call a node of the network a q stage l th critical backtracking node if it is
critical path backtracking and it is preceded in the network by q levels of
backtracking nodes each having more than l edges entering them





Backtracking – An algorithmic search scheme which, in order to compute all
the ways to satisfy a given goal determines a solution by following a series
of branching points until it cannot go any further and then retraces its
steps to the last previous decision in order to compute another possible
solution.

Flow-rate through a movement corridor in a cross country digital map – The
number of vehicles per hour than can pass over a given edge in the network.
This can be calculated as [1/(time it takes a group of vehicles to traverse
the edge)]* number of vehicles in the group.

Maximal flow problem throughput– The problem of determining the greatest
number of vehicles per hour than can travel through a cross-country or road
unit movement network.

Minimal Cost flow problem – The problem (given that each movement edge in the
network has a flow-rate, speed of travel) of determining the best logisitic
routing scheme for a given maximal flow throughput using some measure of cost
such as the sum of the travel times*the edge flow rates for all the edges in
a given routing.



-----------------------------------------



Theorem 1 Given a connected directed graph with a starting node and goal
node and no dead ends. If there are at most ncrit critical backtracking nodes
with at most a q level of prior influence, then the number of different paths
(containing no cycles) form starting to ending is bounded by the expression:

1+(𝑒𝑚𝑎𝑥 −1)∗(𝑛−𝑛1−𝑛𝑐𝑟𝑖𝑡)+(𝑚𝑎𝑥𝑒∗𝑒𝑚𝑎𝑥−1)∗𝑛1𝑐𝑟𝑖𝑡+((𝑚𝑎𝑥𝑒∗𝑒𝑚𝑎𝑥)q-1)*(ncrit-n1crit).



-------------------------------------------





A search step is defined to be one cycle of searches through the database of
edges in order to determine a connected node. Since in generating the queue
of search paths a new path uses the nodes from the prior search paths it is
not necessary to use search steps through the entire edge list again in
starting again more paths











----------------------------------



The theorem is proved by following through the steps of the above search
algorithm and counting the number of ways new paths are generated. Step 2b4
is not necessary if the algorithm is being used to generate all possible
paths (not necessarily in the shortest order). Since 1) the graph is finite,
2) there are no dead ends), 3) the graph is connected, 4) no cycles are
permitted, then each new path will eventually count toward the total.
Considering the way ,as explained in the above slide that the search steps
proceed, the number of paths which the non-critical backtracking nodes enter
into is: A) 1+1∗𝑛2+2∗𝑛3+3∗𝑛4+(𝑗−1)∗𝑛𝑗+…(𝑒𝑚𝑎𝑥−1)∗𝑛𝑚𝑎𝑥𝑒. Using the fact that
n=n1+n2+..nemax we note that the above number is bounded by (emax-1)*(n-n1)+1









---------------------------------



Main Problem to Solve"



In view of other combinatorial formulas for the number of non-cyclic paths in
graphs ,the above formula for the number of backtracked paths in terms of
emax, maxe,ncrit, and q may be able to be simplified using different graph
parameters.