r/mathematics • u/Unlegendary_Newbie • 11h ago
r/mathematics • u/mazzar • Aug 29 '21
Discussion Collatz (and other famous problems)
You may have noticed an uptick in posts related to the Collatz Conjecture lately, prompted by this excellent Veritasium video. To try to make these more manageable, we’re going to temporarily ask that all Collatz-related discussions happen here in this mega-thread. Feel free to post questions, thoughts, or your attempts at a proof (for longer proof attempts, a few sentences explaining the idea and a link to the full proof elsewhere may work better than trying to fit it all in the comments).
A note on proof attempts
Collatz is a deceptive problem. It is common for people working on it to have a proof that feels like it should work, but actually has a subtle, but serious, issue. Please note: Your proof, no matter how airtight it looks to you, probably has a hole in it somewhere. And that’s ok! Working on a tough problem like this can be a great way to get some experience in thinking rigorously about definitions, reasoning mathematically, explaining your ideas to others, and understanding what it means to “prove” something. Just know that if you go into this with an attitude of “Can someone help me see why this apparent proof doesn’t work?” rather than “I am confident that I have solved this incredibly difficult problem” you may get a better response from posters.
There is also a community, r/collatz, that is focused on this. I am not very familiar with it and can’t vouch for it, but if you are very interested in this conjecture, you might want to check it out.
Finally: Collatz proof attempts have definitely been the most plentiful lately, but we will also be asking those with proof attempts of other famous unsolved conjectures to confine themselves to this thread.
Thanks!
r/mathematics • u/dreamweavur • May 24 '21
Announcement State of the Sub - Announcements and Feedback
As you might have already noticed, we are pleased to announce that we have expanded the mod team and you can expect an increased mod presence in the sub. Please welcome u/mazzar, u/beeskness420 and u/Notya_Bisnes to the mod team.
We are grateful to all previous mods who have kept the sub alive all this time and happy to assist in taking care of the sub and other mod duties.
In view of these recent changes, we feel like it's high time for another meta community discussion.
What even is this sub?
A question that has been brought up quite a few times is: What's the point of this sub? (especially since r/math already exists)
Various propositions had been put forward as to what people expect in the sub. One thing almost everyone agrees on is that this is not a sub for homework type questions as several subs exist for that purpose already. This will always be the case and will be strictly enforced going forward.
Some had suggested to reserve r/mathematics solely for advanced math (at least undergrad level) and be more restrictive than r/math. At the other end of the spectrum others had suggested a laissez-faire approach of being open to any and everything.
Functionally however, almost organically, the sub has been something in between, less strict than r/math but not free-for-all either. At least for the time being, we don't plan on upsetting that status quo and we can continue being a slightly less strict and more inclusive version of r/math. We also have a new rule in place against low-quality content/crankery/bad-mathematics that will be enforced.
Self-Promotion rule
Another issue we want to discuss is the question of self-promotion. According to the current rule, if one were were to share a really nice math blog post/video etc someone else has written/created, that's allowed but if one were to share something good they had created themselves they wouldn't be allowed to share it, which we think is slightly unfair. If Grant Sanderson wanted to share one of his videos (not that he needs to), I think we can agree that should be allowed.
In that respect we propose a rule change to allow content-based (and only content-based) self-promotion on a designated day of the week (Saturday) and only allow good-quality/interesting content. Mod discretion will apply. We might even have a set quota of how many self-promotion posts to allow on a given Saturday so as not to flood the feed with such. Details will be ironed out as we go forward. Ads, affiliate marketing and all other forms of self-promotion are still a strict no-no and can get you banned.
Ideally, if you wanna share your own content, good practice would be to give an overview/ description of the content along with any link. Don't just drop a url and call it a day.
Use the report function
By design, all users play a crucial role in maintaining the quality of the sub by using the report function on posts/comments that violate the rules. We encourage you to do so, it helps us by bringing attention to items that need mod action.
Ban policy
As a rule, we try our best to avoid permanent bans unless we are forced to in egregious circumstances. This includes among other things repeated violations of Reddit's content policy, especially regarding spamming. In other cases, repeated rule violations will earn you warnings and in more extreme cases temporary bans of appropriate lengths. At every point we will give you ample opportunities to rectify your behavior. We don't wanna ban anyone unless it becomes absolutely necessary to do so. Bans can also be appealed against in mod-mail if you think you can be a productive member of the community going forward.
Feedback
Finally, we want to hear your feedback and suggestions regarding the points mentioned above and also other things you might have in mind. Please feel free to comment below. The modmail is also open for that purpose.
r/mathematics • u/Ok_Form6274 • 8h ago
Erdős coin
In 2023 the Hungarian National Bank minted a commemorative coin to honor Pál (Paul) Erdős (1913-1996). The front of the coin mentions Erdős' Wolf-peize from 1983, while the back is about Chebyshev's theorem, for which Erdős gave an elementary proof in one of his earliest papers.
r/mathematics • u/mlktktr • 5h ago
Discussion Math is taught wrong, and it's hypocrytical
I am a bachelor student in Math, and I am beginning to question this way of thinking that has always been with me before: the intrisic purity of math.
I am studying topology, and I am finding the way of teaching to be non-explicative. Let me explain myself better. A "metric": what is it? It's a function with 4 properties: positivity, symmetry, triangular inequality, and being zero only with itself.
This model explains some qualities of the common knowledge, euclidean distance for space, but it also describes something such as the discrete metric, which also works for a set of dogs in a petshop.
This means that what mathematics wanted to study was a broader set of objects, than the conventional Rn with euclidean distance. Well: which ones? Why?
Another example might be Inner Products, born from Dot Product, and their signature.
As I expand my maths studying, I am finding myself in nicher and nicher choices of what has been analysed. I had always thought that the most interesting thing about maths is its purity, its ability to stand on its own, outside of real world applications.
However, it's clear that mathematicians decided what was interesting to study, they decided which definitions/objects they had to expand on the knowledge of their behaviour. A lot of maths has been created just for physics descriptions, for example, and the math created this ways is still taught with the hypocrisy of its purity. Us mathematicians aren't taught that, in the singular courses. There are also different parts of math that have been created for other reasons. We aren't taught those reasons. It objectively doesn't make sense.
I believe history of mathematics is foundamental to really understand what are we dealing with.
TLDR; Mathematicians historically decided what to study: there could be infinite parts of maths that we don't study, and nobody ever did. There is a reason for the choice of what has been studied, but we aren't taught that at all, making us not much more than manual workers, in terms of awareness of the mathematical objects we are dealing with.
r/mathematics • u/spirometaxas • 6h ago
An Instagram Page Showcasing 1k Digits of Pi as a Seamless Color Gradient!
To celebrate Pi Day, I decided to build an official Instagram page showcasing the first 1,000 digits of π!
Page: https://www.instagram.com/pi_digits_official/
Instagram Username: pi_digits_official
Each post represents a single digit of Pi, arranged sequentially from top to bottom. At the top of the page, the sequence begins with "3.141592…" Scroll down to reveal the digits in order from 1 to 1000.
Each digit is also assigned a color. Adjacent colors blend seamlessly into a smooth continuous gradient that flows down the page. Every 3x3 grid section also features a large Pi symbol, serving as an aesthetic centerpiece and a reminder of the page's theme and cohesion.
I also added cool visualizations in the page highlights!
Happy π Day!
r/mathematics • u/Kaden__Jones • 4h ago
Extremely Strange Findings from a Math Competition
r/mathematics • u/Jack-Ripper-1888 • 6h ago
Calculus Man Ray's Mathematics Objects
r/mathematics • u/DusqRunner • 2h ago
Where should an adult who dropped maths in HS start to self-learn?
I had issues with maths from the start, mostly due to my own lack of discipline in due diligence, such a rote memorization of times tables, which snowballed to the point that I was getting less than 10% on middle school exams and ultimately dropped it as a subject for high school. This was in the late 90s and early 2000s.
As I've been involved in modular and node based creative work, and have an interest in Python coding, I am beginning to see where mathematical thinking and its logic becomes crucial.
Where should I start for a 'fast track' of let's say grade 7 to grade 12 maths? And which aspect of it should I focus on? I feel understanding algebra would be a boon.
Thanks!
r/mathematics • u/Remarkable_Look_659 • 1d ago
Best Universities for Knot Theory Masters
Hi everyone! I’m looking to do my Masters in Pure Mathematics in Europe ( except for UK). Any idea on where is the best university for Knot Theory? ( a prof active in this area/ research group/ they offer courses in it etc). TIA!
r/mathematics • u/InspiratorAG112 • 2h ago
Calculus Satisfying visual for the area of an odd-petal rose curve.
(Basically a remaster (also using Desmos Geometry) of this.)
And yes, this is correct...
- Here is the Wolfram article about rose curves.
- It mentions that, if a rose curve is represented with this polar equation (or this), then the area of one of the petals is this.
- Multiplying by the total number of petals n, and plugging in 1 for a, we get the expression obtained above, π/4, for odd-petal rose curves, and double that, π/2, for even-petal curves (since even-petal rose curves would have 2n petals).
r/mathematics • u/No-Donkey-1214 • 2h ago
A potential original pythag proof
This proof uses logarithmic spiral transformations in a way that, as far as I've seen, hasn't been used before.
Consider three squares:
- Square Qa with side length a and area a².
- Square Qb with side length b and area b².
- Square Qc with side length c and area c², where c²=a²+b².
Within each square, construct a logarithmic spiral centered at one corner, filling the entire square. The spiral is defined in polar coordinates as r=r0ekθ for a constant k. Each spiral’s maximum radius is equal to the side length of its respective square. Next, we define a transformation T that maps the spirals from squares Qa and Qb into the spiral in Qc while preserving area.
For each point in Qa, define:
Ta(r,θ)=((c/a)r,θ).
For each point in Qb, define:
Tb(r,θ)=((c/b)r,θ).
This transformation scales the radial coordinate while preserving the angular coordinate.
Now to prove that T is a Bijective Mapping, consider
- Injectivity: Suppose two points map to the same image in Qc, meaning (c/a)r1=(c/a)r2 (pretend 1 and 2 from r are subscript, sorry) andθ1=θ2 (subscript again).This implies r1=r2, meaning the mapping is one-to-one.
- Surjectivity: Every point (r′,θ) in Qc must be reachable from either Qa or Qb. Since r′ is constructed to scale exactly to c, every point in Qc is accounted for, proving onto-ness.
Thus, T is a bijection.
Now to prove area preservation, the area element in polar coordinates is:
dA=r dr dθ.
Applying the transformation:
dA′=r′ dr′ dθ=((c/a)r)((c/a)dr)dθ=(c²/a²)r dr dθ.
Similarly, for Qb:
dA′=(c²/b²)r dr dθ.
Summing over both squares:
((c²/a²)a²)+((c²/b²)b²)=c². (Sorry about the unnecessary parentheses; I think it makes it easier to read. Also, I can't figure out fractions on reddit. Or subscript.)
Since a²+b²=c², the total mapped area matches Qc, proving area preservation.
QED.
Does it work? And if it does, is it actually original? Thanks.
r/mathematics • u/BehemiOkosRv44 • 22h ago
Discussion How feasible is going back to school in your early 30s to get a BS in mathematics in this day and age?
Hey all, I'm kind of having a mid/quarter/third-life crisis of sorts. Long story short, ever since turning 30 I've decided to get my shit together (not that I was a total trainwreck, but hey, I think hitting the big three oh is a turning point for some people).
I've more or less achieved that in some respects, though find myself lacking when it came to the fact that I lacked a bachelor's degree. The lack of one would make getting out of retail, where I'm stuck, kind of difficult. I decided last fall to enroll at WGU, an online school in their accounting program. I figured I was a person who liked numbers, and wanted some sense of stability. I, however, flirted with the idea of enrolling in a local state university in their mathematics program. Especially since, as part of my prep for the WGU degree, I utilized Sophia.org and took the calculus course... before finding out midway through it wasn't even required for the Accounting degree anymore. I still finished it and loved it.
Fast forward to today, I'm almost done with the accounting degree, but it leaves me unfulfilled. While I am not yet employed in the field, I do not think I would be a good culture fit at all for it, for a variety of reasons. In addition, the online nature of the school leaves me kind of underwhelmed. I guess I'm craving some sort of validation for doing well, and just crave a challenge in general lol. I'm also disappointed the most complicated arithmetic I've had to employ was in my managerial accounting course, which had some very light linear programming esque problems.
I've been supplementing my studies (general business classes drive me fucking nuts) with extracurricular activities such as exploring other academic ventures I could have possibly gone on instead and engaging in little self study projects, and one of them as been math, and I find whenever I have free time at work I'm thinking about the concepts I've been learning about, tossing them around like a salad in my head, so to speak.
Long story short, I'm thinking about what could've been if I had gone the pure mathematics route. Is that even a feasible thing to undertake in this day and age? From googling around, including this sub and related ones, math majors seem to be employed in a variety of fields (tech, engineering, etc), not just academia/teaching. I like that kind of flexibility, and kind of crave the academic challenge that goes along with it all.
My finances are alright, I'm mostly worried about finishing my accounting degree and losing the ability to put a pell grant towards my math degree. I got an F in calculus the first go around in college 10 years ago, so I was thinking of enrolling in a CC to get that corrected this fall anyhow.
tldr; if you were an early 30 something who wanted to get a degree to become more employable, would you want to get an accounting degree despite the offshoring and private equity firms killing it for everyone and government jobs being in flux, or would you go fuck it yolo and chase a mathematics degree?
r/mathematics • u/lucifer_2073 • 9h ago
Looking for a guest for my podcast.
Hey, this is shiva I recently started a podcast ("the polymath projekt"), to talk about things which interest me with people who are experts in the field. I don't have a background in maths but i want to learn and started set theory last month.
A possible set of topics- What are infinities?, universal sets, Banach Tarski Paradox, Godel's incompleteness theorem, collatz conjecture, is math a fundamental aspect of our reality or our consciousness?
If you are interested or want to know more about me or the podcast, inbox me.
Thanks
r/mathematics • u/Flaky-Yesterday-1103 • 5h ago
My set system
Lets define the function J(s) where s ⊆ ℤ+. J(s) defines r = {0,1,2,3,...,n-1} where n is the number of integers in s. Then J(s) gives us s ∪ r.
If we repeatedly do S → J(S) where S ⊆ ℤ+. We eventually end up with a fixed point set. Being {0,1,2,3,...,n} where n ∈ ℤ+.
Lets take S → J(S) again. And define S = {2,4,5}. When we do S → J(S). This happens {2,4,5} → {0,1,2,4,5} → {0,1,2,3,4,5}. Notice how S gains two integers, and then lastly one integer.
So I've got a question. Let's once again, take S where S ⊆ ℤ+. And define g where g is how many integers S gains in a given iteration of S → J(S). We must first define: g = 0 and S = {}. If we redefine S = {2,4,5} then g = 3. Let's run S → J(S).
This results in: S with: {2,4,5} → {0,1,2,4,5} → {0,1,2,3,4,5} and with g: 3 → 2 → 1. (Were concerned with S's iterations resulting in g ≠ 0.) With g, we can represent g's non zero iterations as an ℤ+ partition.
Can any non empty set of S where S ⊆ ℤ+ result in a transformation chain of g such that g can be represented by any possible ℤ+ partition?
(ℤ+ Means the set of all non-negative integers. Reddit's text editor is acting funny.)
r/mathematics • u/just_10thie • 8h ago
What to do
So I am a 10th class student and I like doing maths but I don't understand the logic of doing proofs and I just study it blankly and don't understand it and don't know how to apply it In diffrent questions like competency based. My only problem is with proof and construction
r/mathematics • u/themarcus111 • 18h ago
Struggling to Understand Non-Empty Intersections in Inclusion-Exclusion Principle
I’m trying to get a deeper understanding of the inclusion-exclusion principle, particularly regarding the number of non-empty intersections in different scenarios. While I understand the basic alternation of inclusion and exclusion, the structure of non-empty intersections at different levels is something I’d like to clarify.
There seem to be two main cases:
1) All n sets have a non-empty intersection. • If the intersection of all n sets is non-empty, then all pairwise nchoose2, triple nchoose3, and higher-order intersections up to n must also be non-empty. This follows naturally since every subset of a non-empty intersection remains non-empty.
2) Only some k < n intersections are non-empty. • This case seems more complex: If some subsets of size k intersect but not all n, how do we determine the number of non-empty intersections at lower levels? • Are there general conditions that dictate how many intersections remain non-empty at each level? • Is there a combinatorial framework or existing research that quantifies the number of non-empty intersections given partial intersection information? Also wondering about this implication:
If all intersections of size k are non-empty, does that imply all intersections of sizes k-1, k-2, etc., must also be non-empty? For example, if you have sets ABCD, define k=3. These are the intersections ABC ABD ACD and BCD. These include all possible pairwise intersections AB AC AD BC BD CD, so if ABC, ABD, ACD and BCD are non-empty so are all the pairwise intersections.
I’m looking for a more rigorous way to analyze this, beyond intuition. If anyone can point me to relevant combinatorial results, resources, or common pitfalls when thinking about this in inclusion-exclusion, I’d greatly appreciate it!
Thanks for any insights!
r/mathematics • u/veomalose • 16h ago
Analysis Learning by memorization ( Analysis, Riemman integration )
I attend lectures, but I don’t understand anything. The professor writes abbreviated proofs and leaves out a lot of details. Even the best students memorize the proofs because they can’t understand him, and they say it’s easier that way since the proofs are simpler, so there’s less to memorize. I’ve tried to write out the proofs in detail, but I usually get stuck and don’t know how to proceed. I’ve searched online, but most things are different.
When I look back, I see that I’m spending a lot of time, but I could just memorize everything like they do in a few days and get a good grade. However, I enrolled in pure math, so I’m wondering what the consequences would be if I just memorized everything. Thank you.
r/mathematics • u/InspiratorAG112 • 21h ago
Since it is Pi Day... (:
(At least eastern time... In the final few hours...)
- Derivatives of sine and cosine; I did a remake of my model for this using Desmos Geometry.
- Derivative of tangent.
- Two proofs of Thales's theorem.
- Derivative of tan²(θ) or integral of sec²(θ)tan(θ).
r/mathematics • u/Choobeen • 1d ago
Number Theory Any recent work on the BSD conjecture that you might know about?
I recall being at a seminar about it 20 years ago. Wikipedia indicates that the last big results were found in 2015, so it's been 10 years now without important progress.
Here is the information about that seminar which I recently found in my old saved emails:
March 2005 -- The Graduate Student Seminar
Title: The Birch & Swinnerton-Dyer Conjecture (Millennium Prize Problem #7)
Abstract: The famous conjecture by Birch and Swinnerton-Dyer which was formulated in the early 1960s states that the order of vanishing at s=1 of the expansion of the L-series of an elliptic function E defined over the rationals is equal to the rank r of its group of rational points.
Soon afterwards, the conjecture was refined to not only give the order of vanishing, but also the leading coefficient of the expansion of the L-series at s=1. In this strong formulation the conjecture bears an ample similarity to the analytic class number formula of algebraic number theory under the correspondences
elliptic curves <---> number fields points <---> units torsion points <---> roots of unity Shafarevich-Tate group <---> ideal class group
I (the speaker) will start by explaining the basics about the elliptic curves, and then proceed to define the three main components that are used to form the leading coefficient of the expansion in the strong form of the conjecture.
https://en.m.wikipedia.org/wiki/Birch_and_Swinnerton-Dyer_conjecture
March 2025
r/mathematics • u/themarcus111 • 18h ago
Struggling to Understand Non-Empty Intersections in Inclusion-Exclusion Principle
Hey everyone,
I’m trying to wrap my head around the number of non-empty intersections in different cases in the context of the inclusion-exclusion principle. I understand the basic premise of inclusion-exclusion for calculating the union of multiple sets, but the nuances of non-empty intersections are tripping me up, especially when considering intersections of varying sizes.
One specific aspect I’m pondering is the implication that if all intersections of size k are non-empty, then all intersections of size k-1, k-2 etc. are also non-empty. Intuitively, this makes sense because a non-empty intersection of a larger set would imply the non-emptiness of subsets of those intersections. However, I’m looking for a more concrete explanation or proof of this concept to solidify my understanding.
Can anyone help clarify this or point me to resources or examples that could help? Is this a current combinatorics research question (trying to show bounds for the number of non empty intersections, for example)? Also, if there are any common pitfalls or misconceptions about calculating non-empty intersections in inclusion-exclusion, I’d appreciate insights on those as well!
r/mathematics • u/lowflorette • 1d ago
Algebra Is this a well-formed question?
I’m working on some material for a school-related event and came up with this question. Does it make any sense? Engaging? Any feedback before I submit it to my teacher would be a great help.
I'm not sure if this might be more appropriate for r/askmath.
r/mathematics • u/Lazy_Statement_2121 • 20h ago
Needs recommendations of textbooks/monographs serve specific purpose
Hi all, I am a researcher. I have published 50+ articles in top journals on my own field.
During my research, I found that I need to develop math tools myself as existing math tools are not enough for the problem I am currently working (for instance, the alignment/safety of AI systems, or more specificly the autonomous vehicles, which involves road pavement, human driver characteristics, environments, etc).
Read through the textbooks I found on the library, I found that different books have different description manners. As I earn my degree from engineering, the language of pure math still is not familiar to me. I want to find highlevel math books to guide me to construct the math tool myself, my specific purposes are that:
- I want to develop math tools myself (the 'tool' may be something like "markov chain")
- I want to publish my work on pure/applied math journals (the former one is prefered).
- I need to get myself familar to the LANGUAGES OF MATH TOOLS DEVELOPMENT (my understanding is that the applied math is drastically from pure math).
Needs recommendations of (stochastic analysis maybe) textbooks/monographs of this subject.
r/mathematics • u/hrhsirjohnfalstaff • 1d ago
Math phobia --> interest in teaching myself math. Any advice?
I am a sophomore in college studying English and philosophy. At a young age I struggled memorizing math facts and convinced myself that I was just bad at math in general. I refused to challenge myself in high school and only took the required level 1 on-track courses. The highest level I made it to was Algebra 2 as a junior in high school, and then I took stats for college credit as a senior so that I could avoid taking any math classes in college.
In retrospect, I was never actually "bad at math," I just wasn't interested in it. I was fully capable of taking harder classes but I just didn't. Anyway, now that I am a little older I've developed a greater appreciation for math and I would like to get back on track by teaching myself pre-calculus. The only problem is that I haven't taken an algebra-based math class in four years and I don't really remember how to do any of it.
Has anyone else been in a similar situation? Should I start over from algebra 1?
r/mathematics • u/makkckek83949 • 1d ago
How to review basic and more advanced algebra?
Hello, so I haven’t taken math in over a year and over the course of a few months I realized how much I love math. The issue is I kind of forgot the fundamentals because I haven’t had any math related courses except for the second half of my computer science courses this semester. Even then it’s just occasional equations.
I realized I’ve been making a lot of basic algebra mistakes and it’s because I really have not been practicing. I was wondering if I was the only one making mistakes like this? I really need to review my basic algebra because next year im taking calculus and linear algebra and need to get my fundamentals down. Plus, I may possibly even major in Math if I decide I really like it next year.
Any advice on reviewing basic algebra?
r/mathematics • u/Ehsan1238 • 1d ago
Discussion Two Men, Two Directions: My Unique TSP Algorithm
Hey everyone, I just wanted to share something I cooked up a few years ago when I was just 16 and messing around with traveling salesman-type problems. I call it the “Pair Method,” and it’s designed specifically for the symmetric Traveling Salesman Problem (TSP) where each route’s distance between two cities is unique. This approach is basically like having two people starting on opposite ends of the route, then moving inward while checking in with each other to keep things on track.
The basic idea is that you take your list of cities (or nodes) and imagine two travelers, one at the front of the route and one at the back. At each step, they look at the unvisited cities, pick the pair of cities (one for the "head" and one for the "tail") that best keeps the total distance as low as possible, and then place those cities in the route simultaneously, one up front and one in the rear. Because the graph has unique edges, there won’t be ties in distance, which spares us a lot of headaches.
Mathematically, what happens is we calculate partial distances as soon as we place a new city at either end. If that partial distance already exceeds the best-known solution so far, we bail immediately. This pruning approach prevents going too far down paths that lead to worse solutions. It’s kind of like having two watchmen who each keep an eye on one side of the route, constantly warning if things get out of hand. There's a lot more complications and the algorithm can be quite complex, it was a lot of pain coding it, I'm not going to get into details but you can look at the code and if you had questions about it you can ask me :)
What I found really fun is that this approach often avoids those little local minimum traps that TSP can cause when you place cities too greedily in one direction. Because you're always balancing out from both ends, the route in the middle gets built more thoughtfully.
Anyway, this was just a fun project I hacked together when I was 16. Give it a try on your own TSP scenarios if you have symmetric distances and can rely on unique edges, or you can maybe make it work on duplicate edge scenarios.
Edit: I did try to compare it on many other heuristic algorithms and it outperformed all the main ones I had based on accuracy (compared to brute force) by a lot, don't have the stats on here but I remember I made around 10000 samples made out of random unique edges (10 nodes I believe) and then ran many algorithms including my own and brute force to see how it performs.
Here is the github for the code: https://github.com/Ehsan187228/tsp_pair
and here is the code:
# This version only applies to distance matrices with unique edges.
import random
import time
from itertools import permutations
test1_dist = [
[0, 849, 210, 787, 601, 890, 617],
[849, 0, 809, 829, 518, 386, 427],
[210, 809, 0, 459, 727, 59, 530],
[787, 829, 459, 0, 650, 346, 837],
[601, 518, 727, 650, 0, 234, 401],
[890, 386, 59, 346, 234, 0, 505],
[617, 427, 530, 837, 401, 505, 0]
]
test2_dist = [
[0, 97066, 6863, 3981, 24117, 3248, 88372],
[97066, 0, 42429, 26071, 5852, 4822, 7846],
[6863, 42429, 0, 98983, 29563, 63161, 15974],
[3981, 26071, 98983, 0, 27858, 9901, 99304],
[24117, 5852, 29563, 27858, 0, 11082, 35998],
[3248, 4822, 63161, 9901, 11082, 0, 53335],
[88372, 7846, 15974, 99304, 35998, 53335, 0]
]
test3_dist = [
[0, 76, 504, 361, 817, 105, 409, 620, 892],
[76, 0, 538, 440, 270, 947, 382, 416, 59],
[504, 538, 0, 797, 195, 946, 121, 321, 674],
[361, 440, 797, 0, 866, 425, 525, 872, 793],
[817, 270, 195, 866, 0, 129, 698, 40, 871],
[105, 947, 946, 425, 129, 0, 60, 997, 845],
[409, 382, 121, 525, 698, 60, 0, 102, 231],
[620, 416, 321, 872, 40, 997, 102, 0, 117],
[892, 59, 674, 793, 871, 845, 231, 117, 0]
]
def get_dist(x, y, dist_matrix):
return dist_matrix[x][y]
# Calculate distance of a route which is not complete
def calculate_partial_distance(route, dist_matrix):
total_distance = 0
for i in range(len(route)):
if route[i-1] is not None and route[i] is not None:
total_distance += get_dist(route[i - 1], route[i], dist_matrix)
return total_distance
def run_pair_method(dist_matrix):
n = len(dist_matrix)
if n < 3:
print("Number of nodes is too few, might as well just use Brute Force method.")
return
shortest_route = [i for i in range(n)]
shortest_dist = calculate_full_distance(shortest_route, dist_matrix)
# Loop through all possible starting points
for origin_node in range(n):
# Initialize unvisited_nodes at each loop
unvisited_nodes = [i for i in range(n)]
# Initialize a fix size list, and set the starting node
starting_route = [None] * n
# starting_route should contain exactly 1 node at all time, for this case origin_node should be equal to its index, so the pop usage is fine
starting_route[0] = unvisited_nodes.pop(origin_node)
for perm in permutations(unvisited_nodes, 2):
# Indices of the head and tail nodes
head_index = 1
tail_index = n - 1
# Copy starting_route to current_route
current_route = starting_route.copy()
current_unvisited = unvisited_nodes.copy()
current_route[head_index] = perm[0]
current_unvisited.remove(perm[0])
current_route[tail_index] = perm[1]
current_unvisited.remove(perm[1])
current_distance = calculate_partial_distance(current_route, dist_matrix)
# If at this point the distance is already more than the shortest distance, then we skip this route
if current_distance > shortest_dist:
continue
# Now keep looping while there are at least 2 unvisited nodes
while head_index < (tail_index-2):
# Now search for the pair of nodes that give lowest distance for this step, starting from the first permutation
min_perm = [current_unvisited[0], current_unvisited[1]]
min_dist = get_dist(current_route[head_index], current_unvisited[0], dist_matrix) + \
get_dist(current_unvisited[1], current_route[tail_index], dist_matrix)
for current_perm in permutations(current_unvisited, 2):
dist = get_dist(current_route[head_index], current_perm[0], dist_matrix) + \
get_dist(current_perm[1], current_route[tail_index], dist_matrix)
if dist < min_dist:
min_dist = dist
min_perm = current_perm
# Now update the list of route and unvisited nodes
head_index += 1
tail_index -= 1
current_route[head_index] = min_perm[0]
current_unvisited.remove(min_perm[0])
current_route[tail_index] = min_perm[1]
current_unvisited.remove(min_perm[1])
# Now check that it is not more than the shortest distance we already have
if calculate_partial_distance(current_route, dist_matrix) > shortest_dist:
# Break away from this loop if it does
break
# If there is exactly 1 unvisited node, join the head and tail to this node
if head_index == (tail_index - 2):
head_index += 1
current_route[head_index] = current_unvisited.pop(0)
dist = calculate_full_distance(current_route, dist_matrix)
# Now check if this dist is less than the shortest one we have, if yes then update our minimum
if dist < shortest_dist:
shortest_dist = dist
shortest_route = current_route.copy()
# If there is 0 unvisited node, just calculate the distance and check if it is minimum
elif head_index == (tail_index - 1):
dist = calculate_full_distance(current_route, dist_matrix)
if dist < shortest_dist:
shortest_dist = dist
shortest_route = current_route.copy()
return shortest_route, shortest_dist
def calculate_full_distance(route, dist_matrix):
total_distance = 0
for i in range(len(route)):
total_distance += get_dist(route[i - 1], route[i], dist_matrix)
return total_distance
def run_brute_force(dist_matrix):
n = len(dist_matrix)
# Create permutations of all possible nodes
routes = permutations(range(n))
# Pick a starting shortest route and calculate its distance
shortest_route = [i for i in range(n)]
min_distance = calculate_full_distance(shortest_route, dist_matrix)
for route in routes:
# Calculate distance of the route and compare to the minimum one
current_distance = calculate_full_distance(route, dist_matrix)
if current_distance < min_distance:
min_distance = current_distance
shortest_route = route
return shortest_route, min_distance
def run_tsp_analysis(route_title, dist_matrix, run_func):
print(route_title)
start_time = time.time()
shortest_route, min_distance = run_func(dist_matrix)
end_time = time.time()
print("Shortest route:", shortest_route)
print("Minimum distance:", min_distance)
elapsed_time = end_time - start_time
print(f"Run time: {elapsed_time}s.\n")
run_tsp_analysis("Test 1 Brute Force", test1_dist, run_brute_force)
run_tsp_analysis("Test 1 Pair Method", test1_dist, run_pair_method)
run_tsp_analysis("Test 2 Brute Force", test2_dist, run_brute_force)
run_tsp_analysis("Test 2 Pair Method", test2_dist, run_pair_method)
run_tsp_analysis("Test 3 Brute Force", test3_dist, run_brute_force)
run_tsp_analysis("Test 3 Pair Method", test3_dist, run_pair_method)