The Traveling Salesman Problem - D-Scholarship@Pitt
THE TRAVELING SALESMAN PROBLEMbyCorinne BrucatoB.A., Sonoma State University, 2010Submitted to the Graduate Faculty ofthe Department of Mathematics in partial fulfillmentof the requirements for the degree ofMaster of ScienceUniversity of Pittsburgh2013
UNIVERSIY OF PITTSBURGHMATHEMATICS DEPARTMENTThis thesis was presentedbyCorinne BrucatoIt was defended onApril 16, 2013and approved byDr. Jeffrey Paul Wheeler, University of Pittsburgh, MathematicsDr. Beverly Michael, University of Pittsburgh, MathematicsDr. Catalin Trenchea, University of Pittsburgh, MathematicsDr. Anna Vainchtein, University of Pittsburgh, MathematicsCommittee Chair: Dr. Jeffrey Paul Wheeler, University of Pittsburgh, Mathematicsii
c by Corinne BrucatoCopyright 2013iii
THE TRAVELING SALESMAN PROBLEMCorinne Brucato, M.S.University of Pittsburgh, 2013Although a global solution for the Traveling Salesman Problem does not yet exist, there are algorithms for anexisting local solution. There are also necessary and sufficient conditions to determine if a possible solutiondoes exist when one is not given a complete graph. This paper gives an introduction to the TravelingSalesman Problem that includes current research. Additionally, the algorithms are used to find a routetraveling through twenty US colleges. As well, we use the Geometric Algorithm to assign scouts for thePittsburgh Pirates.iv
TABLE OF CONTENTS1.0 THE PROBLEM STATED . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .12.0 SOME BASIC GRAPH THEORY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .22.1 Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .22.2 Advanced Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .63.0 THE HISTORY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .104.0 COMPLEXITY CLASSES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .125.0 SOME KNOWN ALGORITHMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .155.1 Nearest-Neighbor Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .155.2 Closest Insertion Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .195.3 Geometric Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .246.0 EXISTENCE OF HAMILTONIAN PATHS AND CYCLES . . . . . . . . . . . . . . . .286.1 Complete Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .286.2 Not Complete Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .297.0 APPLICATIONS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .347.1 Colleges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .347.1.1 Nearest Neighbor and Closest Insertion . . . . . . . . . . . . . . . . . . . . . . . . . .357.1.2 Geometric Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .377.2 Pittsburgh Pirates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .408.0 CONCLUSION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .45BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .46INDEX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .47v
LIST OF FIGURES2.1Tetrahedral Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .22.2Cubical Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .22.3Octahedral Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .32.4Dodecahedral Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .32.5Icosahedral Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .42.6K2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .52.7K3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .52.8Bridge Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .72.9Removed edge gf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .72.10 Removed edge gi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .72.11 Removed edge hi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .72.12 K5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .82.13 Towns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .92.14 Complete Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .92.15 Highlight outer edges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .92.16 Convex Hull of the towns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .93.1Dodecahedron Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .103.2Sample Start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .104.1Brute Force . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .125.1Start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .155.2Stage 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .165.3Stage 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .165.4Stage 3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .165.5Stage 4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .165.6Stage 5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .175.7Stage 6. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .175.8Final . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17vi
5.9Start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .185.10 Stage 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .185.11 Stage 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .185.12 Final . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .185.13 Nearest-Neighbor Pseudocode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .195.14 Start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .195.15 Stage 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .205.16 Stage 3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .205.17 Stage 4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .205.18 Stage 5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .215.19 Stage 6a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .215.20 Stage 7a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .215.21 Stage 8a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .225.22 Stage 6b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .225.23 Stage 7b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .225.24 Stage 8b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .235.25 Closest Insertion Algorithm Pseudocode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .235.26 Stage 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .245.27 Stage 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .245.28 Stage 3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .245.29 Stage 4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .255.30 Stage 5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .255.31 Stage 6. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .255.32 Stage 7. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .265.33 Stage 8. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .265.34 Stage 9. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .265.35 Stage 7. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .265.36 Stage 8. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .265.37 Stage 9. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .265.38 Stage 10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .265.39 Geometric Algorithm Pseudocode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .276.1Each Degree is 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .307.1c 2013 Google, c 2013 Tele Atlas)US Colleges ( . . . . . . . . . . . . . . . . . . . . . . . .347.2c 2013 Google, c 2013 Tele Atlas) . . . . . . . . .Driving Distances Between Each College ( 357.3Nearest Neighbor and Closest Insertion Algorithms on Colleges . . . . . . . . . . . . . . . . .36vii
7.4c 2013Hamiltonian Cycle Using the Nearest Neighbor and Closest Insertion Algorithm ( c 2013 Tele Atlas) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Google, 377.5Stage 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .377.6Stage 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .377.7Stage 3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .377.8Stage 4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .387.9Stage 5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .387.10 Stage 6. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .387.11 Stage 7. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .387.12 Stage 8. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .387.13 Stage 9. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .387.14 Stage 10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .387.15 Stage 11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .387.16 Stage 12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .387.17 Final . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .397.18 Geometric Algorithm on Colleges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .39c 2013 Google, c 2013 Tele Atlas) . . .7.19 Hamiltonian Cycle Using the Geometric Algorithm ( 40c 2013 Google, c 2013 Tele Atlas) . . . . . . . . . . . . . . . . . . . . . . . . . . .7.20 NAME ( 417.21 Group 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .417.22 Group 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .417.23 Group 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .417.24 Group 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .427.25 Group 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .427.26 Group 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .427.27 Group 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .427.28 Group 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .427.29 Group 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .427.30 Group 10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .437.31 Group 11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .437.32 Group 12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .43c 2013 Google, c 2013 Tele Atlas) . . . . . . . . . . . . . . . . . . . . . . . . . . .7.33 Stage 1: ( 437.34 Stage 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .437.35 Stage (n 1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .44c 2013 Google, c 2013 Tele Atlas) . . . . . . . . . . . . . . . . . . . . . . . . . . .7.36 Stage n: ( 44viii
ACKNOWLEDGEMENTSA great number of individuals are owed a debt of gratitude for their contribution to the academic successthat I have attained. The following are but a few of those individuals.First and foremost, I would like to thank Dr. Jeffrey Wheeler of the University of Pittsburgh because absolutely none of this would have been possible without him. Dr. Wheeler walked up to me one day and askedabout my future plans as a graduate student, and when he realized that I had no idea he said,“You are goingto write a thesis, and I am going to be your advisor.” I am so grateful for all of the time that he created outof nowhere in order to be a great advisor. Thank you “all day e’ry day.”Thank you Dr. Beverly Michael, Dr. Catalin Trenchea, and Dr. Anna Vainchtein for going above andbeyond the duties of serving on my committee. Thank you for all of the comments on this thesis, and formaking my days at the University of Pittsburgh a true pleasure.I would like to thank my parents for always believing in me, no matter what my dreams are at any givenmoment. You have shown me what it means to love and have faith, and for that I am grateful.I would like to thank my many support groups around this country. Specifically in Pittsburgh, I wouldlike to thank Marc, Alex, Nadine, Soheil, and Stuart, all of whom have helped me in countless ways. I amamazed that I get to have all of you in my life and I hope that I can be there for you as you have for me.My family members around the country all are constantly supporting me. To Lisa, Lenny, Christine, all ofmy nieces, nephews, and cousins: your love is a blessing. Thank you.Thank you The Dax, Trevor, Kyle, Adam, Brad, Kerri and Fran for being amazing people in my life that Ican always count on although we are far away. I love you all.Thank you to New Hope Church in Cotati, California. I want you to know that I count you as part of myfamily. Thank you for being so warm and inviting. A special “thank you” goes out to Fran, for making theserelationships possible.ix
1.0THE PROBLEM STATEDA traveling salesman wishes to go to a certain number of destinations in order to sell objects. He wants totravel to each destination exactly once and return home taking the shortest total route.Each voyage can be represented as a graph G (V, E) where each destination, including his home, is avertex, and if there is a direct route that connects two distinct destinations then there is an edge betweenthose two vertices. The traveling salesman problem is solved if there exists a shortest route that visits eachdestination once and permits the salesman to return home. (This route is called a Hamiltonian Cycle andwill be explained in Chapter 2.)The traveling salesman problem can be divided into two types: the problems where there is a path betweenevery pair of distinct vertices (no road blocks), and the ones where there are not (with road blocks). Bothof these types of TSP problems are explained in more detail in Chapter 6.Though we are not all traveling salesman, this problem interests those who want to optimize their routes,either by considering distance, cost, or time. If one has four people in their car to drop off at their respectivehomes, then one automatically tries to think about the shortest distance possible. In this case, distanceis minimized. If one is traveling to different parts of the city using the public transportation system, thenminimizing distance might not be the goal, but rather minimizing cost.In the first case, each vertex would be a person’s home, and each edge would be the distance between homes.In the second case, each vertex would be a destination of the city and each edge would be the cost to getfrom one part of the city to the next. Thus, the Traveling Salesman Problem optimizes routes.1
2.0SOME BASIC GRAPH THEORYBefore presenting algorithms and conditions for when a locally optimal solution exists, some basic graphtheory definitions are needed. For an extensive overview of Graph Theory, refer to [1] or [5].2.1BASIC DEFINITIONSThe platonic solids in figures 2.1 through 2.7 will be used to explain some basics of Graph Theory.bbgdcafhcedaFigure 2.1: Tetrahedral GraphFigure 2.2: Cubical GraphDefinition 1. [Simple Graph]A simple graph, G (V,E), is a finite nonempty set V of objects called vertices (singular vertex) together with a possibly empty set E of 2-element subsets of V called edges.All of the figures in Chapter 2 are examples of simple graphs.2
cblfebkmjnsctridaaFigure 2.3: Octahedral GraphpqhdgofeFigure 2.4: Dodecahedral GraphDefinition 2. [Adjacent]Two vertices are adjacent if they are connected by an edge.Definition 3. [Incident]Vertex u and the edge uv are said to be incident with each other. Similarly, v and uv are incident.Vertices b and c in Figure 2.3 are adjacent, while vertices a and f in the same figure are not. In Figure2.4, vertex p and edge pq are incident, but vertex p and edge ae are not.Definition 4. [Degree of a Vertex]The degree of a vertex v (denoted: deg(v)) is the number of vertices in G that are adjacent to v.For example, the vertex a in Figure 2.1 has degree three, while the vertex k in Figure 2.5 has degree 5. Ina simple graph the maximum degree that any vertex can have is one less than the total number of vertices.3
Definition 5. [Minimum and Maximum Degree of a Graph]The maximum degree of a graph, G, is the greatest degree over all of the vertices in G. The minimumdegree of a graph is the least degree over all of the vertices in G. The maximum degree is denoted (G),while the minimum degree is denoted δ(G).For example, let H1 Figure 2.5 and H2 Figure 2.3. Then, (H1 ) 5, and δ(H1 ) 4, and (H2 ) δ(H2 ) 4.Definition 6. [Order and Size of a Graph]The number of vertices in a given graph G, denoted V(G) , is called the order of G and is denoted Ord(G),or G . The number of edges in G, denoted E(G) , is called the size of G.Figures 2.1 through 2.5 have order, 4, 8, 6, 20, and 12, and size 6, 12, 12, 30, and 30, respectively.bhjlgfkideacFigure 2.5: Icosahedr
The platonic solids in figures 2.1 through 2.7 will be used to explain some basics of Graph Theory. b a d c. Figure 2.1: Tetrahedral Graph. g f e h b a d c. Figure 2.2: Cubical Graph. Definition 1. [Simple Graph] A simple graph, G (V,E), is a finite nonempty set V of objects called vertices (singular vertex) to-
Outline LECTURE 1: Traveling Salesman Problem LECTURE 2: Traveling Salesman Problem LECTURE 3: Traveling Salesman Problem Symmetric TSP, Christofides' Algorithm, Removable Edges, Open Problems Asymmetric TSP, Cycle Cover Algorithm, Thin trees
May 02, 2018 · D. Program Evaluation ͟The organization has provided a description of the framework for how each program will be evaluated. The framework should include all the elements below: ͟The evaluation methods are cost-effective for the organization ͟Quantitative and qualitative data is being collected (at Basics tier, data collection must have begun)
Silat is a combative art of self-defense and survival rooted from Matay archipelago. It was traced at thé early of Langkasuka Kingdom (2nd century CE) till thé reign of Melaka (Malaysia) Sultanate era (13th century). Silat has now evolved to become part of social culture and tradition with thé appearance of a fine physical and spiritual .
On an exceptional basis, Member States may request UNESCO to provide thé candidates with access to thé platform so they can complète thé form by themselves. Thèse requests must be addressed to esd rize unesco. or by 15 A ril 2021 UNESCO will provide thé nomineewith accessto thé platform via their émail address.
̶The leading indicator of employee engagement is based on the quality of the relationship between employee and supervisor Empower your managers! ̶Help them understand the impact on the organization ̶Share important changes, plan options, tasks, and deadlines ̶Provide key messages and talking points ̶Prepare them to answer employee questions
Dr. Sunita Bharatwal** Dr. Pawan Garga*** Abstract Customer satisfaction is derived from thè functionalities and values, a product or Service can provide. The current study aims to segregate thè dimensions of ordine Service quality and gather insights on its impact on web shopping. The trends of purchases have
annealing simulation method, as an example of solving a traveling salesman problem. It is known that the traveling salesman problem has a wide application [8]. However, an important feature of these tasks is their large dimension, sometimes over one mil-lion points. The traveling salesman problem belongs to the class NP because it has . , . .
DEATH OF A SALESMAN 1 DEATH OF A SALESMAN TEST (69 Questions) 1. The main character is a salesman who, after thirty-four years with the company, has been taken off salary and is experiencing some personal and financial difficulties. What is his name? a. His name is Willy Loman b. His name is Charley Wills. c. His name is Ben Happs. d.
